class Solution {
public:
    string LCS(string str1, string str2) {
        int length = 0;
        string res = "";
        for (int i = 0; i < str1.length(); i++)
        {
            for (int j = 0; j < str2.length(); j++)
            {
                int temp = 0;
                string temps = "";
                int x = i, y = j;
                while (x < str1.length() && y < str2.length() && str1[x] == str2[y])
                {
                    temps += str1[x];
                    x++;
                    y++;
                    temp++;
                }
                if (length < temp)
                {
                    length = temp;
                    res = temps;
                }
            }
        }
        return res;
    }
};
